package day34;

public class A3 {


    /**
     * 矩阵最长递增路径
     */
    int n,m,ret;
    boolean[][] check; //可有可无
    int[][] memo;
    int[] dx = {1,-1,0,0},dy = {0,0,-1,1};
    public int solve (int[][] matrix) {
        // write code here
        n=matrix.length;m=matrix[0].length;
        check = new boolean[n][m];memo = new int[n][m];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                check[i][j]=true;
                ret = Math.max(dfs(matrix,i,j),ret);
                check[i][j]=false;
            }
        }
        return ret;
    }
    public int dfs(int[][] arr,int i,int j) {
        if(memo[i][j]!=0) return memo[i][j]; //判断（i,j）为起点，是否已有最长序列
        int len = 1; //默认为1
        for(int k=0;k<4;k++) {
            int x=i+dx[k],y=j+dy[k];
            if(x>=0&&x<n&&y>=0&&y<m && arr[x][y]>arr[i][j] && !check[x][y]) {
                check[x][y]=true;
                len = Math.max(len,dfs(arr,x,y)+1); //dfs+1的意思是（i,j）==1,dfs为下一个节点可到达的最长长度
                check[x][y]=false;
            }
        }
        //走到这里，说明走到尽头了
        memo[i][j]=len;
        return len;
    }
}
